#!/usr/bin/python
# -*- coding: utf-8 -*-
'''
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
'''

#class Solution:
def Find(target, array): #array=[[1,2,8,9],[2,4,9,12]]
        col=len(array[0])# 列数4
        row=len(array)   # 行数2
        for i in range(row):
            for j in range(col-1,-1,-1):
                if row==i:
                    break
                if -1==j:
                    break
                if(target==array[i][j]):
                    return 1
                    #break
                if(target<array[i][j]):
                    j-=1
                    continue
                if(target>array[i][j]):
                    i+=1
                    continue
                #tem=array[i][j]
        return 0

target=0
array=[[1,2,8,9],[2,4,9,12]]
print(Find(target,array))